package leetcode.code0132;

import java.util.Arrays;

/**
 * 执行用时：16 ms, 在所有 Java 提交中击败了82.94%的用户
 *
 * 内存消耗：39.8 MB, 在所有 Java 提交中击败了51.57%的用户
 *
 * 通过测试用例：33 / 33
 */
public class Solution4Pass extends Solution132 {

	@Override
	public int minCut(String s) {
		int len = s.length();
		char[] cc = s.toCharArray();
		boolean[][] is = new boolean[len][len];
		int[] dp = new int[len];
		Arrays.fill(dp, Integer.MAX_VALUE);
		for (int i = 0; i < len; i++) {
			is[i][i] = true;
			char left = cc[i];
			for (int j = 0; j < i; j++) {
				char right = cc[j];
				if (j + 1 == i) {
					is[j][i] = (left == right);
				} else {
					is[j][i] = left == right && is[j + 1][i - 1];
				}
			}
			if (is[0][i]) {
				dp[i] = 0;
			} else {
				for (int j = 0; j < i; j++) {
					if (is[j + 1][i]) {
						dp[i] = Math.min(dp[i], dp[j] + 1);
					}
				}
			}
		}
		return dp[len - 1];
	}

	public static void main(String[] args) {
		Solution4Pass so = new Solution4Pass();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();

	}

}
